{ "cells": [ { "cell_type": "markdown", "metadata": { "collapsed": true }, "source": [ "# Graph Theory\n", "## Introduction\n", "Graph theory is a field of mathematics based on mathematical structures called graphs.\n", "A graph is just a diagram made of a set of nodes and a set of edges that join two nodes. The following image illustrates \n", "a graph.\n", "\n", "![graph example](img/graph.png)\n", "\n", "Graphs are abstract objects that humans use to model and design many structures. We can easily relate graphs\n", " with roads and other types of distribution networks, like data networks, or pipelines. We use graphs to illustrate the \n", " organisation of personnel or the hierarchy of the departments in a company, or the layout of a warehouse or of the \n", " production floor plant, so in this sense, graph theory can be applied in many fields.\n", " \n", " Formally, a graph is a pair of sets $G = (N, E)$, where $E$ notes the set of edges and $V$ the set of vertices, which \n", " have the following definitions:\n", " \n", " - **Nodes**: The nodes or vertices of the graph. Normally, it is a finite set and the **order** of a graph is the size \n", " of set, normally noted as *N*. It can also be infinite, as long as it is *numerable,* and we can identify and enumerate\n", " the nodes. Nodes can have different properties. For instance, they can have geographical coordinates, or can be grouped \n", " into different groups. \n", "\n", "- **Edges**: Edges or arcs connecting two different nodes of the graph. Nodes are noted according to the indices of the \n", "nodes they connect. For instance, an edge connecting nodes $i$ and $j$ is noted as $e_{ij}$. Nodes i and j are called \n", "end vertices of $e_{ij}$ and they are said to be **adjacent**. If P is the size of E, we refer to the graph as a P-Graph.\n", "For instance, a graph with 10 edges or arcs is referred to as a 10-Graph.\n", "\n", "Another important definition is a **path**. A path is a set of edges that interconnect different nodes, traversing the graph \n", "possibly through other intermediate nodes.\n", "\n", "## Types of graphs\n", "Let us introduce the following definitions to classify graphs: \n", "- **Weighted graph:** A weighted graph is a graph where each edge $e_{ij}$ has a different *weight* $w_{ij}$. The weight\n", " represents a real world property associated with the graph, and that represents the cost associated to the edge. \n", " For instance, the weight can represent the distance of an edge in a graph that represents a distribution network. \n", " Edges in a weighted graph can have other attributes, like the *capacity* $b_{ij}$. These attributes will be taken into \n", " account when selecting the edges to solve a specific optimization problem. \n", " \n", " ![weighted graph](img/weighted_graph.png)\n", " \n", "- **Directed graph:** In a directed graph, $E$ is a set of ordered pairs of distinct vertices. Normally, a directed graph \n", " is also weighted and the weights of the edges connecting to nodes are not symmetric, that is $w_{ij}$ not equal to $w_{ji}$.\n", " \n", "![directed graph](img/directed_graph.png)\n", "\n", "- **Oriented graph:** An oriented graph is a directed graph with at most one edge interconnecting any two nodes i, j. \n", " That is, if there is an edge $e_{ij}$, there cannot be an edge $e_{ji}. \n", "\n", "![oriented graph](img/oriented_graph.png)\n", "\n", "## Types of problem\n", "### Shorter path \n", "Given a directed graph with positive edge weights (e.g. distance, cost), the shortest path problem aims to find a path\n", "between two given nodes that minimizes the total weight of the edges in the path, which is the sum of the weights of the \n", " edges in the path. \n", "\n", "This problem is important in routing problems, where we need to determine the shortest path between two nodes, when there \n", "might be more than one possible alternative. It is therefore a partial problem in more complex problems in logistic \n", "applications, for instance if we want to establish the best route that minimises the total distance covered by a fleet. \n", "It can also be used to model other situations like minimising the total cost of a sequence of activities (replacing \n", "equipment). \n", "\n", "### Minimum spanning tree\n", "Given a graph with edge weights (e.g. distance, cost), the minimum spanning tree problem aims to find a *spanning tree* \n", "that minimizes the total weight (i.e. the sum of the weights of its edges).\n", "\n", "A spanning tree is a path that interconnects all nodes starting from a root node.\n", "\n", "This problem is typically applied to designing telecommunication networks with a minimum total cost, although it can \n", "also be used to design transport networks, cable TV, distributed systems, to interpret climatological data, among other \n", "applications. \n", "\n", "### Maximal Flow problems\n", "Given a directed graph with edge capacities (e.g. volume/second), maximal flow problems aim to find a *flow* from a given \n", "source node to a given sink node that maximizes the total flow.\n", "\n", "The total flow represents the maximum capacity available in the path connecting the source node and the sink node. \n", "\n", "Maximal flow problems are applied in logistics and distribution problems, but also in other types of applications like \n", "the commercialisation of products in a production–distribution network, programming employment, etc.\n", "\n", "### Minimal cost flow problems\n", "Given a graph with edge weight (e.g. cost) and demands for each node, find a flow satisfying all demands that minimizes\n", " the total cost.\n", " \n", "The minimal cost flow problem can be used to model transportation problems using graphs. \n", "\n", "\n", " \n" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 2 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython2", "version": "2.7.6" }, "pycharm": { "stem_cell": { "cell_type": "raw", "source": [], "metadata": { "collapsed": false } } } }, "nbformat": 4, "nbformat_minor": 0 }